import java.util.ArrayList;
import java.util.List;

/**
 * @author hewei
 * @version 1.0
 * @description: 51. N 皇后
 * @date 2022/7/26 15:06
 */

public class SolveNQueens {

    public static void main(String[] args) {
        SolveNQueens solveNQueens = new SolveNQueens();
        System.out.println(solveNQueens.solveNQueens(5));
    }

    List<Integer> list;
    boolean[] flag;
    int n;
    List<List<String>> ans;
    String s = "";

    public List<List<String>> solveNQueens(int n) {
        list = new ArrayList<>(n);
        this.n = n;
        ans = new ArrayList<>();
        flag = new boolean[n];
        for (int i = 0; i < n - 1; i++) {
            s += ".";
        }
        dfs(0);
        return ans;
    }

    public void dfs(int row) {
        if (row == n) {
            List<String> temp = new ArrayList<>();
            for (Integer integer : list) {
                StringBuilder stringBuilder = new StringBuilder(s);
                stringBuilder.insert(integer, "Q");
                temp.add(stringBuilder.toString());
            }
            ans.add(temp);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (check(row, i)) {
                flag[i] = true;
                list.add(i);
                dfs(row + 1);
                list.remove(list.size() - 1);
                flag[i] = false;
            }
        }
    }

    public boolean check(int row, int col) {
        if (flag[col]) return false;
        for (int i = 0; i < list.size(); i++) {
            Integer index = list.get(i);
            double temp = (index - col) / (double) (i - row);
            if (temp == 1.0 || temp == -1.0) return false;
        }
        return true;
    }
}
